//
// Created by 123 on 2024/3/23.
//
//
// Created by 123 on 2024/3/23.
//
/**
 * 思想：每次选择一条权值最小的边
 * 使这条边的两头联通，
 * 原本已经联通的就不选
 */
#include <iostream>
#include <vector>
#include "../../6_树/并查集/union_look_up_set.cpp"

using namespace std;
#define VexNum 6


typedef struct Edge {
//    弧尾
    int r;
//    弧头
    int h;
//    权值
    int data;
//    是否加入树中
    bool flag;
} Edge;

typedef struct Graph {
    Edge *edges[1000];
    int size = 0;
} Graph;

//图的相关信息
//{99999,     6,         1,          5,          99999,     99999,},
//{6,         99999,     5,          99999,      3,         99999,},
//{1,         5,         99999,      5,          6,         4,    },
//{5,         99999,     5,          99999,      99999,     2,    },
//{99999,     3,         6,          99999,      99999,     6,    },
//{99999,     99999,     4,          2,          6,         99999,},
//下标对应点的信息
string vex[VexNum] = {"V1", "V2", "V3", "V4", "V5", "V6"};

//获得边，其实就是初始化一个边
Edge *getEdge(int  r, int  h, int data);

//添加边，网图中添加边集
void addEdge(Graph &graph, Edge *edge);

//获取下一个未加入树的最小的边
Edge *getNextEdge(Graph &graph);
//初始化数据
void init(Graph &graph);

//核心
vector<string>  kruskal(Graph graph) {
    vector<string> arr;
    while (arr.size() < VexNum - 1) {
        Edge *edge = getNextEdge(graph);
        if(!isSameSet(edge->h,edge->r)){
            arr.push_back(vex[edge->r]+"----->"+vex[edge->h]);
            unionNode(edge->h,edge->r);
        }
    }
    return arr;
}
int main() {
    Graph graph;
    init(graph);

    vector<string> arr= kruskal(graph);
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << "       ";
    }
}


Edge *getNextEdge(Graph &graph) {
    int num = 9999;
    int index = -1;
    for (int i = 0; i < graph.size; ++i) {
        if (!graph.edges[i]->flag&&num > graph.edges[i]->data ) {
            num = graph.edges[i]->data;
            index = i;
        }
    }
    if (index != -1) {
        graph.edges[index]->flag = true;
    }
    return graph.edges[index];
}

void init(Graph &graph){

    addEdge(graph, getEdge(0, 1, 6));
    addEdge(graph, getEdge(1, 4, 3));
    addEdge(graph, getEdge(4, 5, 6));
    addEdge(graph, getEdge(5, 3, 2));
    addEdge(graph, getEdge(3, 0, 5));
    addEdge(graph, getEdge(0, 2, 1));
    addEdge(graph, getEdge(2, 1, 5));
    addEdge(graph, getEdge(2, 3, 5));
    addEdge(graph, getEdge(2, 4, 6));
    addEdge(graph, getEdge(2, 5, 4));
    initUnLoSet();
    add(0);
    add(1);
    add(2);
    add(3);
    add(4);
    add(5);
}

void addEdge(Graph &graph, Edge *edge) {
    graph.edges[graph.size++] = edge;
}

Edge *getEdge(int  r, int  h, int data) {
    Edge *e = (Edge *) malloc(sizeof(Edge));
    e->data = data;
    e->h = h;
    e->r = r;
    e->flag = false;
    return e;
}


